SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Deterministic global optimization</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Deterministic global optimization</span></span>

</h1>

</header>

<p><b>Deterministic global optimization</b> is a branch of mathematical <a href="Optimization" class="mw-redirect" title="Optimization">optimization</a> which focuses on finding the global solutions of an optimization problem whilst providing theoretical guarantees that the reported solution is indeed the global one, within some predefined tolerance. The term "deterministic global optimization" typically refers to <b>complete</b> or <b>rigorous</b> (see below) optimization methods. Rigorous methods converge to the global optimum in finite time. Deterministic global optimization methods are typically used when locating the global solution is a necessity (i.e. when the only naturally occurring state described by a mathematical model is the global minimum of an optimization problem), when it is extremely difficult to find a feasible solution, or simply when the user desires to locate the best possible solution to a problem.

</p>

<div class="mw-heading mw-heading2"><h2 id="Overview">Overview</h2></div>

<p>Neumaier<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> classified global optimization methods in four categories, depending on their degree of rigour with which they approach the optimum, as follows:

</p>

<ul><li>An <b>incomplete</b> method uses clever intuitive heuristics for searching but has no safeguards if the search gets stuck in a local minimum</li>

<li>An <b>asymptotically complete</b> method reaches a global minimum with certainty or at least with probability one if allowed to run indefinitely long, but has no means to know when a global minimizer has been found.</li>

<li>A <b>complete</b> method reaches a global minimum with certainty, assuming exact computations and indefinitely long run time, and knows after a finite time that an approximate global minimizer has been found (to within prescribed tolerances).</li>

<li>A <b>rigorous</b> method reaches a global minimum with certainty and within given tolerances even in the presence of rounding errors, except in near-degenerate cases, where the tolerances may be exceeded.</li></ul>

<p>Deterministic global optimization methods typically belong to the last two categories. Note that building a rigorous piece of software is extremely difficult as the process requires that all the dependencies are also coded rigorously.

</p><p>Deterministic global optimization methods require ways to rigorously bound function values over regions of space. One could say that a main difference between deterministic and non-deterministic methods in this context is that the former perform calculations over regions of the solution space, whereas the latter perform calculations on single points. This is either done by exploiting particular functional forms (e.g. McCormick relaxations<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup>), or using <a href="Interval_analysis" class="mw-redirect" title="Interval analysis">interval analysis</a> in order to work with more general functional forms. In any case bounding is required, which is why deterministic global optimization methods cannot give a rigorous result when working with <a href="Black-box" class="mw-redirect" title="Black-box">black-box</a> code, unless that code is explicitly written to also return function bounds. For this reason, it is common for problems in deterministic global optimization to be represented using a <a href="Directed_acyclic_graph" title="Directed acyclic graph">computational graph</a>, as it is straightforward to overload all operators such that the resulting function values or derivatives yield interval (rather than scalar) results.

</p>

<div class="mw-heading mw-heading2"><h2 id="Classes_of_deterministic_global_optimization_problems">Classes of deterministic global optimization problems</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Linear_programming_problems_(LP)"><a href="Linear_programming" title="Linear programming">Linear programming</a> problems (LP)</h3></div>

<p>Linear programming problems are a highly desirable formulation for any practical problem. The reason is that, with the rise of interior-point algorithms, it is possible to efficiently solve very large problems (involving hundreds of thousands or even millions of variables) to global optimality. Linear programming optimization problems strictly fall under the category of deterministic global optimization.

</p>

<div class="mw-heading mw-heading3"><h3 id="Mixed-integer_linear_programming_problems_(MILP)"><a href="Linear_programming#Integer_unknowns" title="Linear programming">Mixed-integer linear programming</a> problems (MILP)</h3></div>

<p>Much like linear programming problems, MILPs are very important when solving decision-making models. Efficient algorithms for solving complex problems of this type are known and are available in the form of solvers such as <a href="CPLEX" title="CPLEX">CPLEX</a>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Non-linear_programming_problems_(NLP)"><a href="Non-linear_programming" class="mw-redirect" title="Non-linear programming">Non-linear programming</a> problems (NLP)</h3></div>

<p>Non-linear programming problems are extremely challenging in deterministic global optimization. The order of magnitude that a modern solver can be expected to handle in reasonable time is roughly 100 to a few hundreds of non-linear variables. At the time of this writing, there exist no parallel solvers for the deterministic solution of NLPs, which accounts for the complexity gap between deterministic LP and NLP programming.

</p>

<div class="mw-heading mw-heading3"><h3 id="Mixed-integer_non-linear_programming_problems_(MINLP)">Mixed-integer non-linear programming problems (MINLP)</h3></div>

<p>Even more challenging than their NLP counterparts, deterministically solving an MINLP problem can be very difficult. Techniques such as <a href="Cutting-plane_method" title="Cutting-plane method">integer cuts</a>, or branching a problem on its integer variables (hence creating NLP sub-problems which can in turn be solved deterministically), are commonly used.

</p>

<div class="mw-heading mw-heading2"><h2 id="Zero-order_methods">Zero-order methods</h2></div>

<p>Zero-order methods consist of methods which make use of zero-order <a href="Interval_arithmetic" title="Interval arithmetic">interval arithmetic</a>.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup> A representative example is interval bisection.

</p>

<div class="mw-heading mw-heading2"><h2 id="First-order_methods">First-order methods</h2></div>

<p>First-order methods consist of methods which make use of first-order information, e.g., interval gradients or interval slopes.

</p>

<div class="mw-heading mw-heading2"><h2 id="Second-order_methods">Second-order methods</h2></div>

<p>Second-order methods make use of second-order information, usually eigenvalue bounds derived from interval <a href="Hessian_matrices" class="mw-redirect" title="Hessian matrices">Hessian matrices</a>. One of the most general second-order methodologies for handling problems of general type is the <a href="%CE%91%CE%92%CE%92" title="ΑΒΒ">αΒΒ</a> algorithm.

</p>

<div class="mw-heading mw-heading2"><h2 id="Deterministic_global_optimization_solvers">Deterministic global optimization solvers</h2></div>

<ul><li><a href="ANTIGONE" title="ANTIGONE">ANTIGONE</a>: Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations).<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> It is a proprietary software, available through ANTIGONE the <a href="General_Algebraic_Modeling_System" class="mw-redirect" title="General Algebraic Modeling System">GAMS</a> modelling platform.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup></li>

<li><a href="BARON" title="BARON">BARON</a>: BARON is available under the <a href="AIMMS" title="AIMMS">AIMMS</a>, <a href="AMPL" title="AMPL">AMPL</a>, and <a href="General_Algebraic_Modeling_System" class="mw-redirect" title="General Algebraic Modeling System">GAMS</a> <a href="Modeling_language" title="Modeling language">modeling language</a> and on the NEOS Server.<sup id="cite_ref-6" class="reference"><a href="#cite_note-6"><span class="cite-bracket">[</span>6<span class="cite-bracket">]</span></a></sup> It is a proprietary software <sup id="cite_ref-7" class="reference"><a href="#cite_note-7"><span class="cite-bracket">[</span>7<span class="cite-bracket">]</span></a></sup></li>

<li><a href="Couenne" title="Couenne">Couenne</a>: Convex Over and Under ENvelopes for Nonlinear Estimation (Couenne) is an open-source library <sup id="cite_ref-8" class="reference"><a href="#cite_note-8"><span class="cite-bracket">[</span>8<span class="cite-bracket">]</span></a></sup></li>

<li>EAGO: Easy-Advanced Global Optimization (EAGO) <sup id="cite_ref-9" class="reference"><a href="#cite_note-9"><span class="cite-bracket">[</span>9<span class="cite-bracket">]</span></a></sup> is an open-source solver in <a href="Julia_(programming_language)" title="Julia (programming language)">Julia (programming language)</a>. It is developed by the University of Connecticut.<sup id="cite_ref-10" class="reference"><a href="#cite_note-10"><span class="cite-bracket">[</span>10<span class="cite-bracket">]</span></a></sup></li>

<li><a href="LINDO" title="LINDO">LINDO</a> (Linear, Interactive, and Discrete Optimizer) includes global optimization capabilities.<sup id="cite_ref-11" class="reference"><a href="#cite_note-11"><span class="cite-bracket">[</span>11<span class="cite-bracket">]</span></a></sup></li>

<li>MAiNGO: McCormick-based Algorithm for mixed-integer Nonlinear Global Optimization (MAiNGO) <sup id="cite_ref-12" class="reference"><a href="#cite_note-12"><span class="cite-bracket">[</span>12<span class="cite-bracket">]</span></a></sup> is a C++ package with MPI and openMP parallelization and provided open-source <sup id="cite_ref-13" class="reference"><a href="#cite_note-13"><span class="cite-bracket">[</span>13<span class="cite-bracket">]</span></a></sup> under Eclipse Public License - v 2.0.</li>

<li><a href="Octeract_Engine" title="Octeract Engine">Octeract Engine</a> is a proprietary solver with parallelization capabilities. It is developed and licensed by Octeract <sup id="cite_ref-14" class="reference"><a href="#cite_note-14"><span class="cite-bracket">[</span>14<span class="cite-bracket">]</span></a></sup></li>

<li><a href="SCIP_(optimization_software)" class="mw-redirect" title="SCIP (optimization software)">SCIP</a>: SCIP is an open-source suite of optimization solvers which among others solves mixed integer nonlinear programming (MINLP) <sup id="cite_ref-15" class="reference"><a href="#cite_note-15"><span class="cite-bracket">[</span>15<span class="cite-bracket">]</span></a></sup></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

<li id="cite_note-1"><span class="mw-cite-backlink"><b><a href="#cite_ref-1">^</a></b></span> <span class="reference-text">Complete Search in Continuous Global Optimization and Constraint Satisfaction, Acta Numerica 2004 (A. Iserles, ed.), Cambridge University Press 2004</span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><b><a href="#cite_ref-2">^</a></b></span> <span class="reference-text">Computability of global solutions to factorable nonconvex programs: Part I – Convex underestimating problems, Mathematical Programming, 1976, 1(10), 147–175</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><b><a href="#cite_ref-3">^</a></b></span> <span class="reference-text">Hansen, E.R. Global optimization using interval analysis, Marcel Dekker Inc, New York 1992</span>

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFMisenerFloudas2014" class="citation journal cs1"><a href="Ruth_Misener" title="Ruth Misener">Misener, Ruth</a>; <a href="Christodoulos_Floudas" title="Christodoulos Floudas">Floudas, Christodoulos A.</a> (2014). "ANTIGONE: Algorithms for coNTinuous / Integer Global Optimization of Nonlinear Equations". <i>Journal of Global Optimization</i>. <b>59</b> (<span class="nowrap">2–</span>3): <span class="nowrap">503–</span>526. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1007%2Fs10898-014-0166-2">10.1007/s10898-014-0166-2</a>. <a href="Hdl_(identifier)" class="mw-redirect" title="Hdl (identifier)">hdl</a>:<span class="id-lock-free" title="Freely accessible"><a rel="nofollow" class="external text" href="https://hdl.handle.net/10044%2F1%2F15506">10044/1/15506</a></span>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:41823802">41823802</a>.</cite></span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><b><a href="#cite_ref-5">^</a></b></span> <span class="reference-text"><cite class="citation cs2"><a rel="nofollow" class="external text" href="https://www.gams.com/latest/docs/S_ANTIGONE.html"><i>ANTIGONE documentation in GAMS</i></a>, 16 Apr 2013<span class="reference-accessdate">, retrieved <span class="nowrap">27 July</span> 2019</span></cite></span>

</li>

<li id="cite_note-6"><span class="mw-cite-backlink"><b><a href="#cite_ref-6">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://web.archive.org/web/20130629183719/http://www.neos-server.org/neos/solvers/index.html">"BARON on the NEOS Server"</a>. Archived from <a rel="nofollow" class="external text" href="http://www.neos-server.org/neos/solvers/index.html">the original</a> on 2013-06-29<span class="reference-accessdate">. Retrieved <span class="nowrap">2016-01-26</span></span>.</cite></span>

</li>

<li id="cite_note-7"><span class="mw-cite-backlink"><b><a href="#cite_ref-7">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.minlp.com/baron">"The optimization firm"</a>.</cite></span>

</li>

<li id="cite_note-8"><span class="mw-cite-backlink"><b><a href="#cite_ref-8">^</a></b></span> <span class="reference-text">P. Belotti, C. Kirches, <a href="Sven_Leyffer" title="Sven Leyffer">S. Leyffer</a>, J. Linderoth, J. Luedtke and A. Mahajan (2013). Mixed-integer nonlinear optimization. Acta Numerica, 22, pp 1-131. doi:10.1017/S0962492913000032. <a rel="nofollow" class="external free" href="http://journals.cambridge.org/abstract_S0962492913000032">http://journals.cambridge.org/abstract_S0962492913000032</a></span>

</li>

<li id="cite_note-9"><span class="mw-cite-backlink"><b><a href="#cite_ref-9">^</a></b></span> <span class="reference-text"><cite id="CITEREFWilhelmStuber2020" class="citation journal cs1">Wilhelm, M. E.; Stuber, M. D. (2020). <a rel="nofollow" class="external text" href="https://figshare.com/articles/journal_contribution/12849410">"EAGO.jl: easy advanced global optimization in Julia"</a>. <i>Optimization Methods and Software</i>. <b>37</b> (2): <span class="nowrap">425–</span>450. <a href="Doi_(identifier)" class="mw-redirect" title="Doi (identifier)">doi</a>:<a rel="nofollow" class="external text" href="https://doi.org/10.1080%2F10556788.2020.1786566">10.1080/10556788.2020.1786566</a>. <a href="S2CID_(identifier)" class="mw-redirect" title="S2CID (identifier)">S2CID</a> <a rel="nofollow" class="external text" href="https://api.semanticscholar.org/CorpusID:225503302">225503302</a>.</cite></span>

</li>

<li id="cite_note-10"><span class="mw-cite-backlink"><b><a href="#cite_ref-10">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://github.com/PSORLab/EAGO.jl">"EAGO source code"</a>. <i><a href="GitHub" title="GitHub">GitHub</a></i>.</cite></span>

</li>

<li id="cite_note-11"><span class="mw-cite-backlink"><b><a href="#cite_ref-11">^</a></b></span> <span class="reference-text">Linus E. Schrage, Linear, Integer, and Quadratic Programming with Lindo, Scientific Press, 1986, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0894260901</bdi></span>

</li>

<li id="cite_note-12"><span class="mw-cite-backlink"><b><a href="#cite_ref-12">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="http://permalink.avt.rwth-aachen.de/?id=729717">"McCormick-based Algorithm for mixed-integer Nonlinear Global Optimization (MAiNGO)"</a>.</cite></span>

</li>

<li id="cite_note-13"><span class="mw-cite-backlink"><b><a href="#cite_ref-13">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://git.rwth-aachen.de/avt.svt/public/maingo">"MAiNGO source code"</a>.</cite></span>

</li>

<li id="cite_note-14"><span class="mw-cite-backlink"><b><a href="#cite_ref-14">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://octeract.com/documentation/">"Octeract"</a>.</cite></span>

</li>

<li id="cite_note-15"><span class="mw-cite-backlink"><b><a href="#cite_ref-15">^</a></b></span> <span class="reference-text"><cite class="citation web cs1"><a rel="nofollow" class="external text" href="https://www.scipopt.org/">"SCIP optimization suite"</a>.</cite></span>

</li>

</ol></div></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2024-08-20" href="https://en.wikipedia.org/wiki/?title=Deterministic_global_optimization&oldid=1241316126">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>